#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void RadixSort1 (vector<int>& v) {
	int len = v.size();
	vector<int> counting(19, 0);
	vector<int> result(len, 0);

	//1.找出最长位数
	int max = 0;
	for(auto& t : v) {
		if(max < abs(t))
			max = abs(t);
	}
	int max_digit_length = 0;
	while(max) {
		max_digit_length++;
		max /= 10;
	}

	int dev = 1;
	for(int i = 0; i < max_digit_length; i++) {
		//2. 计算基数
		for(auto& t : v) {
			int radix = t / dev % 10 + 9;
			counting[radix]++;
		}
		//3. 按照基数进行计数排序
		counting[0]--;
		for(int j = 1; j < counting.size(); j++) {
			counting[j] += counting[j-1];
		}
		for(int j = len - 1; j >= 0; j--) {
			int radix = v[j] / dev % 10 + 9;
			result[counting[radix]--] = v[j];
		}
		v = result;
		//counting.clear();我tm裂开，这个直接将所有元素擦除了，size = 0
		std::fill(counting.begin(), counting.end(), 0);
		dev *= 10;
	}
}

/*
void RadixSort1 (vector<int>& v) {
	int len = v.size();
	vector<int> counting(19, 0);
	vector<int> result(len, 0);

	//1.找出最长位数
	int max = 0;
	for(auto& t : v) {
		if(max < abs(t))
			max = abs(t);
	}
	int max_digit_length = 0;
	while(max) {
		max_digit_length++;
		max /= 10;
	}

	int dev = 1;
	for(int i = 0; i < max_digit_length; i++) {
		//2. 计算基数
		for(auto& t : v) {
			int radix = t / dev % 10 + 9;
			counting[radix]++;
		}
		//3. 按照基数进行计数排序
		for(int j = 1; j < counting.size(); j++) {
			counting[j] += counting[j-1];
		}
		for(int j = len - 1; j >= 0; j--) {
			int radix = v[j] / dev % 10 + 9;
			result[--counting[radix]] = v[j];
		}
		v = result;
		//counting.clear();我tm裂开，这个直接将所有元素擦除了，size = 0
		std::fill(counting.begin(), counting.end(), 0);
		dev *= 10;
	}
}*/

//MSD方法
void RadixSort2 (vector<int>& v) {
}

int main() {
	vector<int> v{1,4,3,2,7,9,5,10,6,3};
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	RadixSort1(v);
	//RadixSort2(v);
	for(auto& t : v)
		cout << t << " ";
	cout << endl;
	return 0;
}
